/**
题目:
    给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
    示例 1：
    输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。
    示例 2：
    输入: "cbbd"
    输出: "bb"
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/longest-palindromic-substring
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路:
    动态规划
*/
class Solution {
public:
    string longestPalindrome(string s) {
        //这是个dp问题
        //dp[i][j],表示字符串i到j的回文长度
        /*
        状态转移方程
        dp[i][j]=dp[i+1][j-1]+a[i]==a[j]
        */
        int size=s.size();
         int maxLen=0;
         int start=0;
        string res;
        vector<vector<int>> dp(size,vector<int>(size,0));
        for(int i=size-1;i>=0;i--){
            dp[i][i]=1;
            for(int j=i;j<size;j++){
                 //j<=i+1,说明[i,i+1],[i,i]
                dp[i][j]=s[i]==s[j]&&(j-i<=1||dp[i+1][j-1]);
                
               if(dp[i][j]>0&&j-i+1>maxLen){
                    maxLen=j-i+1;
                    start=i;
                }
            }
        }
        return  s.substr(start,maxLen);;
    }
};